package com.hy.treeNode3;

import com.hy.treeNode.TreeNode;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class ValueOfLeftLeaves {
    private int Deep;
    private int val;

    /**
     * 513.找树左下角的值
     * 力扣题目链接
     *
     * 给定一个二叉树，在树的最后一行找到最左边的值。
     *
     * 思路
     * 本地要找出树的最后一行找到最左边的值。此时大家应该想起用层序遍历是非常简单的了，反而用递归的话会比较难一点。
     *
     * 我们依然还是先介绍递归法。
     * 递归
     * 我们来分析一下题目：在树的最后一行找到最左边的值。
     * 首先要是最后一行，然后是最左边的值。
     *
     * 如果使用递归法，如何判断是最后一行呢，其实就是深度最大的叶子节点一定是最后一行。
     *
     *
     * @param root
     * @return
     */
    // 递归法
    public Integer valueOfLeftLeaves2(TreeNode root){
        val = root.val;
        findLeftValue(root,0);
        return val;
    }

    public void findLeftValue(TreeNode root,int deep){
        if (root == null){
            return;
        }
        if (root.left == null && root.right == null){
            // deep  树的深度
            if (deep > Deep){
                val = root.val;
                Deep = deep;
            }
        }

        if (root.left != null){
            findLeftValue(root.left, deep+1);
        }

        if (root.right != null){
            findLeftValue(root.right,deep+1);
        }
    }
     // 迭代法
    public Integer valueOfLeftLeaves(TreeNode root){
        Deque<TreeNode> deque = new LinkedList<>();
        int res = 0;
        if (root == null){
            return null;
        }
        deque.offerLast(root);
        while (!deque.isEmpty()){
            int len = deque.size();
            for (int i = 0; i < len; i++) {
                TreeNode node = deque.pollFirst();
                // 索引为0;则是一层中最左边的节点
                if (i == 0){
                    res = node.val;
                }
                if (node.left != null){
                    deque.offerLast(node.left);
                }
                if(node.right != null){
                    deque.offerLast(node.right);
                }
            }
        }
        return res;
    }



    public static void main(String[] args) {
        TreeNode leftNode1 = new TreeNode(1, null, null);
        TreeNode rightNode1 = new TreeNode(2, null, null);

        TreeNode leftNode2 = new TreeNode(6, null, null);
        TreeNode rightNode2 = new TreeNode(8, null, null);

        TreeNode leftNode = new TreeNode(4, leftNode1, rightNode1);
        TreeNode rightNode = new TreeNode(7, leftNode2, rightNode2);

        TreeNode root = new TreeNode(5, leftNode, rightNode);

        ValueOfLeftLeaves val = new ValueOfLeftLeaves();
        System.out.println("树最左下角的值（迭代）："+val.valueOfLeftLeaves(root));
        System.out.println("树最左下角的值（递归）："+val.valueOfLeftLeaves2(root));

    }
}
